#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        int n = triangle[m - 1].size();

        // 其实这题有点巧妙，
        // 可以复用动态规划数组
        int f[n];

        // 首先统计最后一行路径的长度
        for (int i = 0; i < n; i++) {
            f[i] = triangle[m - 1][i];
        }

        // 从倒数第二行开始
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                // 每个位置的长度，等于下一行 j 或者 j + 1 的长度加上当前长度中的最小值
                // 因为这里状态转移公式只依赖 j + 1，更新自身的同时不影响其他位置的计算
                // 因此可以复用动态规划的数组，所以说这题有点巧妙
                f[j] = min(f[j], f[j + 1]) + triangle[i][j];
            }
        }

        return f[0];
    }
};